As to clustering technique (signal classification technique), a cluster (set) of samples as targets for identification is classified into each class (subset) of samples having similar feature. For example, this clustering technique is applied to processing to identify targets such as characters, figures, or speeches. As to a face image as a target for identification, if the face image is correctly identified, one class includes only face images of the same person, and each class comprises speech data of different speaker. In order to realize this identification processing with high accuracy, not only feature extraction but also clustering is important.
In non-patent references 1˜3, clustering is performed on the assumption that samples belonging to the same class are closely distributed in a feature space. Concretely, a feature of each sample is updated to a center of distribution of classes (potentially existing) neighboring the sample. By collecting samples belonging to the same class at one position, clustering is realized. In non-patent reference 1, each sample is updated to be most similar to a mean feature of samples (neighbor samples) of which similarity between features thereof is above a threshold. In this case, as to calculation of the mean feature, the higher the number of dimensions of the feature space is, the more the calculation load increases.
In non-patent references 2 and 3, how each sample is near a center of distribution of classes (potentially existing) is represented by a density surrounding each sample. For example, the density is approximated as the number of adjacent samples. Each sample is updated to have a high density and the most similarity above a threshold. The feature is updated using the density. Accordingly, in comparison with non-patent reference 1, the calculation load can be reduced.
As to non-patent references 2 and 3, in order for each sample to execute calculation processing of density and determination processing of samples classified into the same class, similarity between samples is necessary. These two processing cannot be executed simultaneously. In order to effectively execute two processing without overlapping the operation, similarity information between two samples of all combinations need be stored into a memory (buffer). Accordingly, a memory having large capacity (square-order of the number of samples) is necessary.
Furthermore, in order to effectively calculate density of each sample, sample ID and similarity (above a threshold) of neighbor samples may be stored. However, the number of neighbor samples cannot be previously predicated. In addition to this, if the threshold is minimum, all samples can be neighbor samples of each sample. Accordingly, even if the sample ID and the similarity are stored, a memory having square-order of the number of samples is necessary.    [Non-patent reference 1] “Mode-seeking by Medoidshifts”, Y. A. Sheikh, E. A. Khan and T. Kanade, IEEE International Conference on Computer Vision, 2007.    [Non-patent reference 2] “A Graph-theoretic approach to nonparametric cluster analysis”, W. L. G. Koontz, P. Narendra, and K. Fukunaga, IEEE Trans. on Computer, c-25 (9), 1976.    [Non-patent reference 3] “Quick Shift and Kernel Methods for Mode Seeking”, A. Vedaldi and S. Soatto, ECCV2008, PartIV, LNCS5305, pp. 705-718, 2008.